package com.lwl.Algorithmic_data_structure.class18暴力递归2动态规划;

/**
 * @author lwl
 * @Description 给一个一维数组充当纸牌，现在两个绝顶聪明的人，只能从开始和末尾取牌，一人一次，请问赢的人总共多少字牌数
 * @date 2023/6/6 22:31
 */
public class Code02CardInLine {

    public static void main(String[] args) {
        int[] arr = {5, 7, 4, 5, 8, 1, 6, 0, 3, 4, 6, 1, 7};
        System.out.println(cardsInLine(arr));
        System.out.println(cardsInLine2(arr));
        System.out.println(cardsInLine3(arr));
    }

    static private int cardsInLine3(int[] cards) {
        int[][] firstMap = new int[cards.length][cards.length];
        int[][] secondMap = new int[cards.length][cards.length];
        for (int i = 0; i < cards.length; i++) {
            firstMap[i][i] = cards[i];
            // 这一步多余默认就是0，写一下
            secondMap[i][i] = 0;
        }

        // 左上到右下的对角线，然后这条对角线往右上移动的
        for (int startCol = 1; startCol < cards.length; startCol++) {
            // 行都是从第0行开始
            int left = 0;
            // 列是从1开始递增的
            int right = startCol;
            while (right < cards.length) {
                firstMap[left][right] = Math.max(cards[left] + secondMap[left + 1][right], cards[right] + secondMap[left][right - 1]);
                secondMap[left][right] = Math.min(firstMap[left + 1][right], firstMap[left][right - 1]);
                left++;
                right++;
            }
        }
        return Math.max(firstMap[0][cards.length - 1], secondMap[0][cards.length - 1]);
    }

    static private int cardsInLine2(int[] cards) {
        int[][] firstMap = new int[cards.length][cards.length];
        int[][] secondMap = new int[cards.length][cards.length];

        for (int i = 0; i < cards.length; i++) {
            for (int j = 0; j < cards.length; j++) {
                firstMap[i][j] = -1;
                secondMap[i][j] = -1;
            }
        }

        return Math.max(firstTake2(cards, 0, cards.length - 1, firstMap, secondMap), secondTake2(cards, 0, cards.length - 1, firstMap, secondMap));
    }

    private static int firstTake2(int[] cards, int left, int right, int[][] firstMap, int[][] secondMap) {
        if (firstMap[left][right] != -1) {
            return firstMap[left][right];
        }

        int ans = 0;

        if (left == right) {
            ans = cards[left];
        } else {
            int takeLeft = secondTake2(cards, left + 1, right, firstMap, secondMap) + cards[left];
            int takeRight = secondTake2(cards, left, right - 1, firstMap, secondMap) + cards[right];
            // 自己先手肯定会领大
            ans = Math.max(takeLeft, takeRight);
        }
        firstMap[left][right] = ans;
        return ans;
    }

    private static int secondTake2(int[] cards, int left, int right, int[][] firstMap, int[][] secondMap) {
        if (secondMap[left][right] != -1) {
            return secondMap[left][right];
        }
        //        if (left == right) {
        //            return 0;
        //        }
        int ans = 0;
        if (left != right) {
            //对手拿了左边的
            int takeLeft = firstTake2(cards, left + 1, right, firstMap, secondMap);
            //对手拿了右边的
            int takeRight = firstTake2(cards, left, right - 1, firstMap, secondMap);
            // 因为对手是绝顶聪明的，所以下一次选择只能选较小的结果
            ans = Math.min(takeLeft, takeRight);
        }
        secondMap[left][right] = ans;
        return ans;
    }


    static private int cardsInLine(int[] cards) {
        return Math.max(firstTake(cards, 0, cards.length - 1), secondTake(cards, 0, cards.length - 1));
    }

    private static int firstTake(int[] cards, int left, int right) {
        if (left == right) {
            return cards[left];
        }
        int takeLeft = secondTake(cards, left + 1, right) + cards[left];
        int takeRight = secondTake(cards, left, right - 1) + cards[right];
        // 自己先手肯定会领大
        return Math.max(takeLeft, takeRight);
    }

    private static int secondTake(int[] cards, int left, int right) {
        if (left == right) {
            return 0;
        }
        //对手拿了左边的
        int takeLeft = firstTake(cards, left + 1, right);
        //对手拿了右边的
        int takeRight = firstTake(cards, left, right - 1);
        // 因为对手是绝顶聪明的，所以下一次选择只能选较小的结果
        return Math.min(takeLeft, takeRight);
    }

}
